#include <iostream>
using namespace std;
struct ListNode
{
	int value;
	ListNode *next;	
};

int listLength(ListNode *p)
{
	int length = 0;
	while(p)
	{
		p = p->next;
		++length;
	}
	return length;
}

ListNode *findCommonListNode(ListNode *pa,ListNode *pb)
{
	while(pa && pb && pa != pb)
	{
		pa = pa->next;
		pb = pb->next;
	}
	return pa;
}

ListNode *findCommonListNodeInLists(ListNode *headA,ListNode *headB)
{
	ListNode *pa = headA, *pb = headB;
	int lengthA = listLength(pa), lengthB = listLength(pb);

	if(lengthA > lengthB)
	{
		int i = lengthA - lengthB;
		while(i>0)
		{
			pa = pa->next;
			--i;
		}
	}
	else
	{
		int i = lengthB - lengthA;
		while(i>0)
		{
			pb = pb->next;
			--i;
		}
	}
	return findCommonListNode(pa,pb);
}

ListNode *createList(int arr[],int length)
{
	if(arr == nullptr || length <=0)
		return nullptr;
	ListNode *head = new ListNode;
	head->value = arr[0];
	head->next = nullptr;
	ListNode *p = head;
	for(int i = 1; i< length;++i)
	{
		ListNode *next = new ListNode;
		next->value = arr[i];
		next->next = nullptr;
		p->next = next;
		p = next;
	}
	return head;
}

void linkLists(ListNode *&headA, ListNode *&headB,int arr[],int length)
{
	if(arr == nullptr || length <=0)
		return;
	ListNode *pa = headA, *pb = headB;
	while(pa && pa->next)
	{
		pa = pa->next;
	}
	while(pb && pb->next)
	{
		pb = pb->next;
	}
	ListNode *head = new ListNode;
	head->value = arr[0];
	head->next = nullptr;
	ListNode *p = head;
	for(int i = 1 ; i < length; ++i)
	{
		ListNode *next = new ListNode;
		next->value = arr[i];
		next->next = nullptr;
		p->next = next;
		p = next;
	}
	if(pa)
		pa->next = head;
	else
		headA = head;
	if(pb)
		pb->next = head;
	else
		headB = head;
}
int main()
{

	int arr1[] = {1,2,5,7,9,12};
	int arr0[] = {12,5,7,6,12,8};
	int arrCommon[] = {3,5,9};

	ListNode *headA = createList(arr1,0);
	ListNode *headB = createList(arr0,0);
	linkLists(headA,headB,arrCommon,3);

	ListNode *common = findCommonListNodeInLists(nullptr,nullptr);
	if(common == nullptr)
		cout<<"no common" <<endl;
	else
		cout<<common->value<<endl;
	system("pause");
	return 0;
}